#include <bits/stdc++.h>
using namespace std;

/*
1900. 最佳运动员的比拼回合
已解答
困难
相关标签
premium lock icon
相关企业
提示
n 名运动员参与一场锦标赛，所有运动员站成一排，并根据 最开始的 站位从 1 到 n 编号（运动员 1 是这一排中的第一个运动员，运动员 2 是第二个运动员，依此类推）。

锦标赛由多个回合组成（从回合 1 开始）。每一回合中，这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。

例如，当前回合中，运动员 1, 2, 4, 6, 7 站成一排
运动员 1 需要和运动员 7 比拼
运动员 2 需要和运动员 6 比拼
运动员 4 轮空晋级下一回合
每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。

编号为 firstPlayer 和 secondPlayer 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以 裁定 谁是这一回合的获胜者。

给你三个整数 n、firstPlayer 和 secondPlayer 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的 最早 回合数和 最晚 回合数。

 

示例 1：

输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]
解释：
一种能够产生最早回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：2, 3, 4, 5, 6, 11
回合 3：2, 3, 4
一种能够产生最晚回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：1, 2, 3, 4, 5, 6
回合 3：1, 2, 4
回合 4：2, 4
示例 2：

输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]
解释：两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。
 

提示：

2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n
*/

// 法一
class Solution {
public:
    using ll = long long;
    vector<int> earliestAndLatest(int n, int first, int second) {
        if (first > second) swap(first, second);
        first--; second--; // 转为0基索引
        unordered_map<ll, pair<int, int>> memo;
        auto [e, l] = dfs(n, first, second, 1, memo);
        return {e, l};
    }

private:
    // 状态键：压缩n、first位置、second位置、当前回合
    ll getKey(int n, int f, int s, int r) {
        return (static_cast<ll>(n) << 24) | (static_cast<ll>(f) << 16) | (static_cast<ll>(s) << 8) | r;
    }

    pair<int, int> dfs(int n, int f, int s, int r, unordered_map<ll, pair<int, int>>& memo) {
        ll key = getKey(n, f, s, r);
        if (memo.count(key)) return memo[key];

        // 若当前轮相遇，直接返回当前回合
        if (f + s == n - 1) {
            return memo[key] = {r, r};
        }

        // 对称性优化：转换到左半部分处理
        int mid = n / 2;
        if (s < mid) {
            return dfs(n, n-1-s, n-1-f, r, memo);
        }

        int min_e = INT_MAX, max_l = INT_MIN;
        int mask_cnt = 1 << (n / 2); // 非关键比赛结果枚举

        for (int mask = 0; mask < mask_cnt; ++mask) {
            vector<int> next; // 下一轮晋级者

            // 处理每对对决
            for (int i = 0; i < n / 2; ++i) {
                int left = i, right = n-1 - i;
                bool has_f = (left == f || right == f);
                bool has_s = (left == s || right == s);
                if (has_f && has_s) continue; // 已相遇，跳过
                // 关键选手必胜，其他按掩码决定
                next.push_back(has_f ? f : (has_s ? s : (mask & (1<<i) ? left : right)));
            }

            // 奇数时中间轮空晋级
            if (n % 2) {
                int mid_pos = n / 2;
                next.push_back(mid_pos == f || mid_pos == s ? mid_pos : mid_pos);
            }

            sort(next.begin(), next.end()); // 按原始编号排序

            // 找下一轮中f和s的新位置
            int nf = -1, ns = -1;
            for (int i = 0; i < next.size(); ++i) {
                if (next[i] == f) nf = i;
                if (next[i] == s) ns = i;
            }
            if (nf == -1 || ns == -1) continue; // 若任一淘汰，跳过

            // 递归计算下一轮
            auto [e, l] = dfs(next.size(), nf, ns, r+1, memo);
            min_e = min(min_e, e);
            max_l = max(max_l, l);
        }

        return memo[key] = {min_e, max_l};
    }
};

// 法二
class Solution {
public:
    // 主函数：计算两位运动员相遇的最早和最晚回合
    vector<int> earliestAndLatest(int n, int first, int second) {
        // 确保first编号小于second（利用对称性简化处理，避免重复计算）
        if (first > second) swap(first, second);
        // 将1基编号转为0基索引（便于数组位置计算）
        first--; second--;
        // 记忆化存储：key为压缩的状态信息，value为{最早回合, 最晚回合}
        unordered_map<long long, pair<int, int>> memo;
        // 调用递归函数计算结果，并转换为vector返回
        auto [earliest, latest] = dfs(n, first, second, 1, memo);
        return {earliest, latest};
    }

private:
    // 生成唯一状态键：将n(人数)、first位置、second位置、当前回合压缩为long long
    // 目的是唯一标识当前状态，避免重复计算（记忆化核心）
    long long getKey(int n, int first, int second, int round) {
        return (static_cast<long long>(n) << 24) |  // n占高24位（最大n为28，足够存储）
               (static_cast<long long>(first) << 16) |  // first位置占8位（0~255足够）
               (static_cast<long long>(second) << 8) |  // second位置占8位
               round;  // 当前回合占8位（回合数不会超过log2(n)+1，足够）
    }

    // 递归函数：探索当前状态下的最早和最晚相遇回合
    // 参数：n-当前轮人数；first-当前轮first位置；second-当前轮second位置；round-当前回合数；memo-记忆化表
    pair<int, int> dfs(int n, int first, int second, int round, unordered_map<long long, pair<int, int>>& memo) {
        // 生成当前状态的唯一键，检查是否已计算过（记忆化查询）
        long long key = getKey(n, first, second, round);
        if (memo.count(key)) return memo[key];  // 已计算过，直接返回结果

        // 核心判断：若当前轮中两人位置对称（i和n-1-i），说明本轮相遇
        // 原因：每轮中第i名与倒数第i名对决，此时两人直接对决，相遇回合为当前轮
        if (first + second == n - 1) {
            return memo[key] = {round, round};  // 最早和最晚均为当前回合
        }

        // 对称性优化：若second在左半部分（前n/2个位置），通过镜像转换减少状态量
        // 镜像规则：位置i → n-1-i，此时两人相对关系不变，结果等价
        if (second < n / 2) {
            return dfs(n, n - 1 - second, n - 1 - first, round, memo);
        }

        // 初始化当前状态的最早和最晚回合（用极值便于后续更新）
        int min_earliest = INT_MAX;  // 最早回合：取所有可能路径的最小值
        int max_latest = INT_MIN;    // 最晚回合：取所有可能路径的最大值

        // 枚举所有非关键比赛的结果（关键比赛指包含first/second的对决，结果固定）
        // 非关键比赛有n/2组，每组有2种可能，共2^(n/2)种组合（用mask枚举）
        int mask_count = 1 << (n / 2);  // 掩码总数：2的(n/2)次方

        for (int mask = 0; mask < mask_count; ++mask) {
            vector<int> next;  // 存储下一轮晋级的运动员（原始编号）

            // 处理当前轮的每一组对决（第i组：左位置i vs 右位置n-1-i）
            for (int i = 0; i < n / 2; ++i) {
                int left = i;         // 左运动员位置
                int right = n - 1 - i; // 右运动员位置

                // 关键比赛处理：若组内有first，first必赢（规则：相遇前必胜）
                if (left == first || right == first) {
                    next.push_back(first);
                }
                // 关键比赛处理：若组内有second，second必赢
                else if (left == second || right == second) {
                    next.push_back(second);
                }
                // 非关键比赛：根据mask决定胜者（mask第i位为1则左赢，0则右赢）
                else {
                    next.push_back((mask & (1 << i)) ? left : right);
                }
            }

            // 处理奇数人数的情况：中间位置的运动员轮空直接晋级
            if (n % 2 == 1) {
                next.push_back(n / 2);  // 中间位置编号为n/2（0基）
            }

            // 下一轮运动员按原始编号升序排列（题目规则：获胜者重新排序）
            sort(next.begin(), next.end());

            // 查找first和second在下一轮中的新位置
            int new_first = -1, new_second = -1;
            for (int i = 0; i < next.size(); ++i) {
                if (next[i] == first) new_first = i;   // first的新位置
                if (next[i] == second) new_second = i; // second的新位置
            }

            // 若first或second未晋级（理论上不可能，因关键比赛必赢，此处防异常）
            if (new_first == -1 || new_second == -1) continue;

            // 递归计算下一轮的结果（回合数+1）
            auto [e, l] = dfs(next.size(), new_first, new_second, round + 1, memo);
            // 更新当前状态的最早回合（取所有路径的最小值）
            min_earliest = min(min_earliest, e);
            // 更新当前状态的最晚回合（取所有路径的最大值）
            max_latest = max(max_latest, l);
        }

        // 记忆化存储当前状态的结果（避免重复计算）
        memo[key] = {min_earliest, max_latest};
        return memo[key];
    }
};